﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode100Hot.笔试.掌趣科技
{

    public  class SolZQ2{

       public int  Fbnq(int i)
        {


            int[] dp = new int[i+1];
            if (i == 0)
            {
                return 0;
            }
            if (i == 1)
            {
                return 1;
            }
            dp[0] = 0;
            dp[1] = 1;
            for (int j = 2; j <= i; j++)
            {
                dp[j] = dp[j-1]+ dp[j - 2];
            }
            return dp[i];

        }

        public int Fib(int n)//递归法
        {
            if (n == 0)
            {
                return 0;
            }
            if (n == 1)
            {
                return 1;
            }

            return Fib(n - 1) + Fib(n - 2);
    }
    }
    internal class 非递归实现斐波那契数列
    {



        static void MainZQ2(string[] args)

        {

SolZQ2 s = new SolZQ2();
            Console.WriteLine(s.Fbnq(0));
            Console.WriteLine(s.Fib(4));

        }



    }
}
